import java.net.PortUnreachableException;
import java.security.PublicKey;
import java.util.List;
import java.util.Scanner;

public class test1 {
    /**
     * level1：环形链表进行判断是否存在环结构
     * level2::环形链表判断入口的位置
     * level3：环形链表计算在环中的元素的个数
     * @param args
     */
    public static void main(String[] args) {
        // 直接快慢指针进行查找
        Scanner in=new Scanner(System.in);
        System.out.print("请输入链表的长度: ");
        int n=in.nextInt();
        int []a=new int[n];

        // 输入到链表中的数据
        System.out.print("给出具体的数据: ");
        for(int i=0;i<n;i++){
            a[i]=in.nextInt();
        }
        // 创建并打印生成的含有环的链表
        // create()方法已经实现了

        //创建含有环的位置p
        System.out.print("请输入环pos的位置: ");
        int p=in.nextInt();
        ListNode v1=createNodeList.create(a,p);
        Print.print(v1,n);
        System.out.println();

        // 测试输入的链表关系：
        // 1 2 3 4 5 2
        // 创建新的链表关系
//        ListNode v2=new ListNode(1);
//        v2.next=new ListNode(2);
//        v2.next.next=new ListNode(3);
//        v2.next.next.next=new ListNode(4);
//        v2.next.next.next.next=new ListNode(5);
//        v2.next.next.next.next.next = v2.next;

        // 1. 测试是否含有环结构
        boolean test = hasCycle(v1);
        //打印
        System.out.println("是否含有环结构: "+test);

        // 2. 测试找到环的入口
        ListNode inn=CycleOut(v1);
//        System.out.println(inn.val);
        System.out.println("环中的入口元素位置为："+getPosition(v1,inn));
        System.out.println("环入口处的元素值为："+inn.val);

        // 3. 找到环中的元素个数
        int cnt=CycleNumber(v1);
        System.out.println("环中的元素个数有（算上入口的节点）："+cnt);
    }

    // 判断链表中是否存在环
    public static boolean hasCycle(ListNode head){
        if(head==null || head.next==null){
            return false;
        }
        ListNode slow=head;
        ListNode fast=head.next;
        while(slow!=fast){
            if(fast==null || fast.next==null){
                return false;
            }
            slow=slow.next;
            fast=fast.next.next;
        }
        return true;
    }

    // 直接输出环的入口
    public static ListNode CycleOut(ListNode head){
        if (head == null || head.next == null) {
            return null; // 无环或者链表为空，返回null表示没有环
        }
        ListNode slow = head;
        ListNode fast = head;
        boolean hasCycle = false;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }

        if (!hasCycle) {
            return null; // 无环，返回null表示没有环
        }

        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow;

    }


    //直接给出环中的元素个数(算上入口的节点)
     public static int CycleNumber(ListNode head){
         if(head==null || head.next==null){
             return 0;
         }
         ListNode slow=head;
         ListNode fast=head.next;

         int count = 1; // 计数器初始值为1，因为fast已经指向了slow的下一个节点

         while(slow!=fast) {
             if (fast == null || fast.next == null) {
                 return 0;
             }
             slow = slow.next;
             fast = fast.next.next;
         }

         // 统计环中的节点个数
         fast=fast.next;  // fast向后移动一步，指向slow的下一个节点
         while(slow!=fast){
             fast=fast.next;
             count++;
         }
         return count;
    }

    // 辅助计算位置
    private static int getPosition(ListNode head, ListNode target) {
        int pos = 0;
        ListNode current = head;
        while (current != target) {
            current = current.next;
            pos++;
        }
        return pos;
    }

}

